package fireway;

/**
 * 希尔排序
 * 2018年 07月 21日 星期六
 *
 * @author fireway
 */
public class ShellSort {
    private long mLArray[];

    private int mSize;

    public ShellSort(int initialCapacity) {
        mLArray = new long[initialCapacity];
        mSize = 0;
    }

    public void insert(int value) {
        mLArray[mSize++] = value;
    }

    public void display() {
        System.out.print("[");
        for (int i = 0; i < mSize; i++) {
            System.out.print(mLArray[i]);
            if (i != mSize - 1) {
                System.out.print(", ");
            }
        }
        System.out.print("]\n");
    }

    public void shellSort() {
        int h = 1;
        do {
            h = h * 3 + 1;
        } while (h < ((mSize - 1) / 3));

        for (; h > 0; h = (h - 1) / 3) {
            for (int i = h; i < mSize; i++) {
                long temp = mLArray[i];
                int j = i;
                for (; j > h - 1 && mLArray[j - h] >= temp; j -= h) {
                    mLArray[j] = mLArray[j - h];
                }
                mLArray[j] = temp;
            }
        }
    }
}
